package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

/**
 * 希尔排序
 */
public class ShellSort {

    /**
     * 希尔插入排序，类似于直接插入排序，直接插入排序的比较间隔为 1
     * @param array 原数组，执行完后数组内容改变
     * @param dk 增量（比较间隔）
     */
    public static void shellInsertSort(int[] array, int dk) {
        for (int i = dk; i < array.length; i++) {
            // 新插入的元素小于前面的元素，需要插入到前面的位置，需要找到待插入新元素的位置
            // 待插入的元素
            int x = array[i];
            // 元素逐个后移，直到 j 为待插入的位置
            int j = i;
            while (j >= dk && x < array[j - dk]) {
                array[j] = array[j - dk];
                j -= dk;
            }
            array[j] = x;
        }
    }

    /**
     * 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
     * 1. 选择一个增量序列 (t1,t2,...,ti,tj,...,tk)，其中 (ti>tj,tk=1)
     * 2. 按增量序列个数 k，对序列进行 k 趟排序
     * 3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序
     * 4. 仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
     * @param array 原数组，执行完后数组内容改变
     */
    public static void shellSort(int[] array) {
        System.out.print("排序前：");
        ArrayUtils.printArray(array);
        // 增量 dk 初始设置为数组长度的一半，每次插入排序后减半
        int dk = array.length / 2;
        while (dk > 0) {
            shellInsertSort(array, dk);
            dk /= 2;
        }
        System.out.print("排序后：");
        ArrayUtils.printArray(array);
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        shellSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        shellSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        shellSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }

}
